{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Maximum Pair Sum in Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minPairSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中最大数对和的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个数对 <code>(a,b)</code> 的 <strong>数对和</strong> 等于 <code>a + b</code> 。<strong>最大数对和</strong> 是一个数对数组中最大的 <strong>数对和</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，如果我们有数对 <code>(1,5)</code> ，<code>(2,3)</code> 和 <code>(4,4)</code>，<strong>最大数对和</strong> 为 <code>max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个长度为 <strong>偶数</strong> <code>n</code> 的数组 <code>nums</code> ，请你将 <code>nums</code> 中的元素分成 <code>n / 2</code> 个数对，使得：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums</code> 中每个元素 <strong>恰好</strong> 在 <strong>一个</strong> 数对中，且</li>\n",
    "\t<li><strong>最大数对和</strong> 的值 <strong>最小</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你在最优数对划分的方案下，返回最小的 <strong>最大数对和</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,5,2,3]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>数组中的元素可以分为数对 (3,3) 和 (5,2) 。\n",
    "最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,5,4,2,4,6]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。\n",
    "最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n</code> 是 <strong>偶数</strong> 。</li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-maximum-pair-sum-in-array](https://leetcode.cn/problems/minimize-maximum-pair-sum-in-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-maximum-pair-sum-in-array](https://leetcode.cn/problems/minimize-maximum-pair-sum-in-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,2,3]', '[3,5,4,2,4,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)//2):\n",
    "            if nums[i]+nums[len(nums)-1-i] > ans:\n",
    "                ans = nums[i]+nums[len(nums)-1-i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        temp = []\n",
    "        while nums:\n",
    "            temp.append(nums.pop()+nums.pop(0))\n",
    "        return max(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums) // 2):\n",
    "            res = max(res, nums.pop() + nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        temp = list()\n",
    "        for i in range(len(nums)//2):\n",
    "            temp.append(nums.pop())\n",
    "        res = list()\n",
    "        for i in range(len(temp)):\n",
    "            res.append(temp[i]+nums[i])\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        maxhq = nums.copy()\n",
    "        heapq._heapify_max(maxhq)\n",
    "        heapq.heapify(nums)\n",
    "        length = len(nums)//2\n",
    "        ans = -float('inf')\n",
    "        while length>0:\n",
    "            last = heapq.heappop(nums)+heapq._heappop_max(maxhq)\n",
    "            ans = max(last,ans)\n",
    "            length-=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        sum_ = -inf\n",
    "        p = 0\n",
    "        q = len(nums)-1\n",
    "        while p < q:\n",
    "            sum_ = max(sum_, nums[p]+nums[q])\n",
    "            p += 1\n",
    "            q -= 1\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l,r = 0,len(nums) - 1\n",
    "        while l < r:\n",
    "            ans = max(nums[l] + nums[r],ans)\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i,j=0,len(nums)-1\n",
    "        max_=0\n",
    "        while i<j:\n",
    "            max_=max(max_,nums[i]+nums[j])\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        res=0\n",
    "        for i in range(n//2):\n",
    "            res=max(nums[i]+nums[n-i-1],res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return max(nums[i] + nums[j] for i, j in enumerate(range(n - 1, n // 2 - 1, -1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        # 大的配小的\n",
    "        nums.sort()\n",
    "        return max(nums[i] + nums[-i - 1] for i in range(len(nums) // 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max([nums[i] + nums[len(nums) - 1 - i] for i in range(len(nums) // 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n//2):\n",
    "            ans = max(ans,nums[i] + nums[n-1-i])\n",
    "        return ans;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return max(nums[i]+nums[-1-i] for i in range(n>>1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            ans = max(ans, nums[l] + nums[r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            print(nums[i],nums[n-i-1])\n",
    "            ret = max(ret,nums[i]+nums[n-i-1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minPairSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        q=deque(nums)\n",
    "        res=-inf\n",
    "        while q:\n",
    "            a=q.popleft()\n",
    "            b=q.pop()\n",
    "            res=max(res,a+b)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
